The field of information security deals with methods and mechanisms to protect sensitive information. Some of these methods and mechanisms deal with the problem of maintaining the integrity of information while it is in storage or in transit, others deals with the issue of ensuring that the information is available only to authorized entities and access is denied to entities not so authorized. Several of the methods and mechanisms used in the field of information security are based on the use of Cryptographic Algorithms. Table lookup is a fundamental primitive used by many cryptographic algorithms such as the Data Encryption Standard (DES), Advanced Encryption Standard (AES) , the popular A3/A8 algorithm used in GSM cell-phones which is known as COMP128 etc. Table lookups are also used by some non-cryptographic algorithms in the field of information security. For example, universal hash functions are traditionally not considered to be cryptographic algorithms although they are used for ensuring the integrity of information and some universal hash functions are based on table lookups. Thus, Table lookup is an important primitive used in the field of information security.
In its simplest form, a Table is a collection of data values wherein each of said data values in said collection has a distinct index. The Table lookup operation then comprises of obtaining the data value that corresponds to a supplied index. The total amount of memory needed to store a Table, that is, to store the entire collection of data values is referred to as the lookup table size. In addition, the total number of distinct indices in the collection, which by definition is the number of data values in the collection, is referred to as the table lookup index size. For any given table T, hereinafter, we shall use the notation T[i] to refer to the data value that corresponds to the index i. Thus although the present application is described in terms of tables and table lookup operations it includes all means of representing collections of data such as arrays, matrices, ordered sets, lists, groups, collections etc.
Implementing the Table lookup primitive in situations where information security is not an issue is usually straightforward. In fact, Table lookup is such a basic primitive that many general purpose computing platforms have specialized hardware to assist in this operation, for example many microprocessors have an indexed addressing mode where one supplies the location of a table in the memory of a computing system and an index into the table and the hardware retrieves the data value corresponding to the index.
However, in situations where information security is an issue, implementing a Table lookup is substantially harder. This is because this operation has to be performed on some information processing equipment which is a physical system. The Table lookup operation that has to be performed could involve information which is sensitive in nature and disclosure of this information or part thereof to unauthorized entities must be prevented. For example, the index being accessed in the Table lookup operation and/or the data value corresponding to the index could be sensitive. All physical information processing systems leak information about their internal states into the physical environment in which they are placed. Such leakage occurs in a variety of ways. For example, the instantaneous power consumption of a system conveys information about the operations being carried out by the device at that time, the timing of certain operations conveys information about the operations, the electromagnetic emissions from a device carry information about the operations being done on the device, etc. In the field of information security it is customary to call these additional sources of information as Side-Channels. It is well known that information security can be seriously compromised if Side-Channel information is available to unauthorized entities. In fact, there is a large class of attacks, known in the literature, in which an unauthorized entity gets sensitive information by exploiting side-channel information, some examples being Timing attacks (TA), Simple Power Analysis attacks (SPA), Differential Power Analysis attacks (DPA), Simple Electromagnetic Analysis attacks (SEMA), Differential Electromagnetic Analysis attacks (DEMA), higher-order DPA, higher-order DEMA etc. Hereinafter we will use the generic term side-channel attacks to include all attacks which involve analysis of any side-channel. This term includes TA, SPA, DPA SEMA, DEMA etc. We use the generic term, higher-order side-channel attacks, to include all attacks which involve the analysis of multiple side-channels or multiple sections the same side-channel or both. This generic term includes higher-order DPA, higher-order DEMA etc. Therefore, if a Table lookup involving sensitive information is to be performed within a physical system then special care must be taken to limit the information leakage from various Side-Channels in the scenario where an unauthorized entity can have access to these Side-Channels. This makes the implementation of a Table lookup much more complex in this scenario. In addition, implementing Table lookup on resource constrained information processing devices such as chip cards, cryptographic tokens etc., poses a special challenge since these devices are less shielded from the environment and therefore have larger leakage of information via various side-channels. In general, it is reasonable to assume that in performing a table lookup the information obtained via the side channel is statistically related to each bit of the index being addressed and to each bit of the data value corresponding to the index.
Many mechanisms and countermeasures are known in prior art, have been proposed to reduce the effectiveness of side-channel exposures in constrained information processing devices. These fall into two main categories. In the first category are physical protection methods which try to reduce the amount of information leakage from the device itself, e.g., the use of physical shielding and techniques for hardware design which minimize the leakage of information. Use of these techniques result in devices which inherently leak less information on the side-channels than devices which are not thus protected. However, the leakage is not entirely eliminated. In most situations, even after the application of these physical protections, there is enough information leakage so that implementations of information security techniques on such devices can be attacked using statistical side-channel attacks such as DPA, DEMA, higher-order DPA, higher-order DEMA etc. To overcome this problem, there is another category of protection mechanisms which are based on reducing the effectiveness of the information that does leak on the side-channels. These type of protections require a careful implementation of information security techniques on the device, where the implementation is quite different from the obvious and direct implementations of the technique. Most of these latter protection mechanisms are either based on or similar to a generic method and technique outlined in, “Towards Sound Approaches to Counteract Power Analysis Attacks,” authored by Suresh Chari, Charanjit S. Jutla, Josyula R. Rao and Pankaj Rohatgi, which appears in proceedings of “Advances in Cryptology-CRYPTO '99”, Lecture Notes in Computer Science, # 1666, published by Springer, Pages 398–412, which is incorporated herein by reference in entirety for all purposes. The present invention can be viewed as a substantial improvement to the table lookup scheme suggested in that publication. Since the present invention of a space-efficient, side-channel attack resistant table lookup mechanism would be part of a larger side-channel attack resistant implementation of any information security technique which involves table lookups as well as other operations, we now describe the generic method and technique, hereinafter referred to as the “General Countermeasure Against Side-channel Attacks” which is disclosed in the aforementioned publication. The next few paragraph is an adaptation from the original paper which described the technique and is therefore put in quotes.
“A General Countermeasure
A General Countermeasure Against Side-Channel Attacks is to ensure that the adversary cannot predict any relevant bit of information from the side-channel in any clock cycle, without making run-specific assumptions independent of the actual inputs to a computation. This makes statistical tests involving several experiments impossible, since the chance of the adversary making the correct assumptions for each run is extremely low. While this yields secure computation, it is not clear how one can do effective computation under this requirement since no bit depending directly on the data and key can be manipulated at any cycle. In some cases the function being computed has algebraic properties that permits such an approach, e.g., for RSA one could use the well known blinding technique to partially hide the actual values being manipulated. Another class of problems where this is possible is the class of random self-reducible problems. Such structure is unlikely to be present in primitives such as block ciphers.”
“Encoding
The encoding we propose is to randomly split every bit of the original computation, into k shares where each share is equiprobably distributed and every proper subset of (k−1) shares is statistically independent of the encoded bit. Computation can then be carried securely by performing computation only the shares, without ever reconstructing the original bit. Shares are refreshed after every operation involving them to prevent information leakage to the adversary.”
“To fix a concrete encoding scheme, we assume that each {\em bit} is split into k shares using any scheme which has the required stochastic properties. For instance, bit b can be encoded as the k shares b⊕r1, r2, . . . , rk−1, r1⊕ . . . ⊕rk−1, where the ri 's are randomly chosen bits. Furthermore, assume that each share is placed in a separate word at a particular bit position and all other bits of the share word are chosen uniformly at random.”
“in practice, it would be more useful, if each word of computation is split similarly into k shares. In that case, other schemes of splitting into shares based on addition mod 256, subtraction mod 256 would also be viable. Encoding bytes of data manipulated by splitting them into shares would yield the optimal performance. Ignoring the initial setup time, the performance penalty in performing computation using just the k shares is a factor of k. Our results which have been proved based on the bit encoding scheme would also work for this case but the bounds they yield are based only on the characteristics of the noise within the chip, and hence may not be optimal. This is discussed briefly after the analysis for the bit encoding case. The results and analysis we present here can serve as a framework in which to prove results for the byte encoding scheme.”
“The method to encode the bit in secret shares should be chosen based on the computation being protected. For instance, for an implementation of DES, the XOR scheme is ideal since the basic operations used are XOR, permutations, and table lookups. Table lookups can be handled by first generating a random rearrangement of the original table since a randomized index will be used to look up the table. This step increases the overhead beyond the factor of 2.”
“In practice, the splitting technique needs to be applied only for a sufficient number of steps into the computation until the adversary has very low probability of predicting bits, i.e., till sufficient secret key dependent operations have been carried out. Similar splitting also has to be done at end of the computation if the adversary can get access to its output. For instance, in DES, one needs to use the splitting scheme only for the first four and last four rounds.”
Thus, the above publication provides a general countermeasure against side-channel attacks, which is to split each bit or word of the computation into k shares (where k is any integer such as 2, 3, 4, . . . , etc.) with specific statistical properties. Hereinafter we will refer to any such mechanism to split any bit or word in a computation to be a “secret-sharing operation”. Thus the countermeasure for any information security techniques will work by splitting all inputs into shares using a secret-sharing operation, performing computation on the shares to obtain shares of the output and then recombining the shares of the output using the inverse of secret-sharing operation to produce the output. However, the mechanism proposed to deal with Table lookups, which is to create a random rearrangement of the original table (which has to be in RAM ) is inefficient, since the random rearrangement of a table in RAM will take as much space as the size of the table. Thus in prior art, reducing the exposures from side-channels during table lookups has been the most challenging since many good countermeasures require much more Read/Write memory (such as RAM) than these devices can spare. Further, the limited addressing capabilities of such devices often complicates lookups of large tables, sometimes leading to new side-channel exposures. For example, many smart cards have a total of only 256–512 bytes of RAM. A significant part of this memory is required for the regular functioning of these smart cards and therefore only a fraction of this total RAM can be made available for countermeasures against side channel leakage. In many scenarios, the amount of RAM available for countermeasures, which is hereinafter referred to as available RAM is significantly less than the lookup table size. For example the COMP 128 algorithm requires lookup of a table of size 512 bytes and index size of 512 and several other smaller tables, and the DES algorithm requires the lookup of eight tables of size 64 bytes and index size 64 each for a total of 256 bytes. Many chip cards have no more than 256 bytes of RAM and the available RAM is even smaller and this means that good known countermeasures cannot be applied to such cards to protect against side channel attacks for algorithms such as DES, COMP 128 etc. In addition many smart cards are 8-bit machines and can lookup indices only within the range 0 to 255 , within a table of bytes at any one time. This leads to problems if the smart card is required to access a table of bytes with larger index size than 256. For example, the COMP 128 table with 512 byte table size and index size of 512 cannot be looked up in a single operation on such a chip card and any such operation has to be implemented as a sequence of operations. Having a sequence of operations to implement a Table lookup opens up additional avenues for attack using side-channels. As a result of these limitations, heretofore side-channel attack resistant implementations many algorithms which utilized the Table lookup operation required the use of more expensive devices which had more RAM, or these implementations were either unacceptably slow or are still susceptible to side channel attacks.
The terms set and subset as used herein is used as in mathematics. Thus, a set refers to a collection of elements. A subset of a set refers to another collection of zero or more elements from said set including the total set.